package com.gaogzhen.datastructure.graph.directed;

import com.gaogzhen.datastructure.stack.Stack;
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.TransitiveClosure;

import java.util.Iterator;

/**
 *  计算强连通分量
 * @author gaogzhen
 */
public class KosarajuSharirSCC {

    /**
     * 访问标记
     */
    private boolean[] marked;

    /**
     * 连通分量标记
     */
    private int[] id;

    /**
     * 连通分量数量
     */
    private int count;

    /**
     * 计算强连通分量
     * @param digraph 有向图
     */
    public KosarajuSharirSCC(Digraph digraph) {

        // compute reverse postorder of reverse graph
        DepthFirstOrder dfs = new DepthFirstOrder(digraph.reverse());

        // run DFS on digraph, using reverse postorder to guide calculation
        marked = new boolean[digraph.V()];
        id = new int[digraph.V()];
        for (int v : dfs.reversePost()) {
            if (!marked[v]) {
                dfs(digraph, v);
                count++;
            }
        }

        // check that id[] gives strong components
        assert check(digraph);
    }

    /**
     * 深度优先搜索计算强连通分量
     * @param digraph   优先图
     * @param s 起点
     */
    private void dfs(Digraph digraph, int s) {
        // 栈记录搜索路径
        Stack<Iterator<Integer>> path = new Stack<>();
        if (!marked[s]) {
            // 起点未标记，标记计数加1
            // 起点默认没标记，可以不加是否标记判断
            marked[s] = true;
            id[s] = count;
            Iterable<Integer> iterable = digraph.adj(s);
            Iterator<Integer> it;
            if (iterable != null && (it = iterable.iterator()) != null){
                // 顶点对应的邻接表迭代器存入栈
                path.push(it);
            }
        }
        while (!path.isEmpty()) {
            Iterator<Integer> it = path.pop();
            int x;
            while (it.hasNext()) {
                // 邻接表迭代器有元素，获取元素
                x = it.next();
                if (!marked[x]) {
                    // 顶点未被标记，标记计数+1
                    marked[x] = true;
                    id[x] = count;
                    if (it.hasNext()) {
                        // 邻接表迭代器有元素重新入栈
                        path.push(it);
                    }
                    // 深度优先原则，当前迭代器入栈，新标记顶点的邻接表迭代器入栈，下次循环优先访问
                    Iterable<Integer> iterable = digraph.adj(x);
                    if (iterable != null && (it = iterable.iterator()) != null){
                        path.push(it);
                    }
                    break;
                }
            }

        }
    }

    /**
     * 连通分量数量
     * @return 连通分量数量
     */
    public int count() {
        return count;
    }

    /**
     * 顶点v和w是强连通的吗
     * @param  v 顶点v
     * @param  w 顶点w
     * @return {@code true} if vertices {@code v} and {@code w} are in the same
     *         strong component, and {@code false} otherwise
     * @throws IllegalArgumentException unless {@code 0 <= v < V}
     * @throws IllegalArgumentException unless {@code 0 <= w < V}
     */
    public boolean stronglyConnected(int v, int w) {
        validateVertex(v);
        validateVertex(w);
        return id[v] == id[w];
    }

    /**
     * 顶点v所在的强连通分量标记
     * @param  v 指定顶点v
     * @return the component id of the strong component containing vertex {@code v}
     * @throws IllegalArgumentException unless {@code 0 <= s < V}
     */
    public int id(int v) {
        validateVertex(v);
        return id[v];
    }

    /**
     *
     * @param digraph 有向图
     * @return
     */
    private boolean check(Digraph digraph) {
        TransitiveClosure tc = new TransitiveClosure(digraph);
        for (int v = 0; v < digraph.V(); v++) {
            for (int w = 0; w < digraph.V(); w++) {
                if (stronglyConnected(v, w) != (tc.reachable(v, w) && tc.reachable(w, v))) {
                    return false;
                }
            }
        }
        return true;
    }

    /**
     * 校验顶点v
     * @param v 顶点v
     */
    private void validateVertex(int v) {
        int V = marked.length;
        if (v < 0 || v >= V) {
            throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
        }
    }
}